/*
Date:20210417 13:02pm
key:set维护滑动窗口，新学到一个lower_bound低约束
*/
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> st;
        //遍历每个数字
        for (int i = 0; i < nums.size(); i++) {
            //寻找在排序中第一个大于等于x>=nums[i] - t.找不到返回st.end()
            auto lb = st.lower_bound((long)nums[i] - t);
            //找到并且满足*lb <= (long)nums[i] + t就返回1
            if (lb != st.end() && *lb <= (long)nums[i] + t) return 1;
            //每个新元素都要插入树中
            st.insert(nums[i]);
            //遍历到k时树就满了，因此以后每次都要用i-k处的元素搜索然后删除。
            //因为是插入前做的比较，因此最多只有k-1个元素在set里
            if (i >= k) st.erase(nums[i - k]);
        }
        return 0;
    }
};
